package main

import "strings"

// 22. 括号生成
func main() {
	num := 3
	parenthesis := generateParenthesis(num)
	for _, str := range parenthesis {
		println(str)
	}
}

func generateParenthesis(n int) []string {
	// 回溯，并且保证右边的括号，不能少于左边的括号
	left, right := "(", ")"
	leftSum := 0
	rightSum := 0

	totalLen := 2 * n

	var res []string
	var tempStr []string

	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == totalLen {
			res = append(res, strings.Join(tempStr, ""))
			return
		}

		if leftSum < n {
			tempStr = append(tempStr, left)
			leftSum++
			dfs(idx + 1)
			tempStr = tempStr[:len(tempStr)-1]
			leftSum--
		}

		if leftSum > rightSum {
			tempStr = append(tempStr, right)
			rightSum++
			dfs(idx + 1)
			tempStr = tempStr[:len(tempStr)-1]
			rightSum--
		}
	}

	dfs(0)

	return res
}

/*
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8
*/
